#include <bits/stdc++.h>
using namespace std;
typedef int ElemType;

/*
    LNode:链表结点
*/
typedef struct LNode {
    ElemType data;
    struct LNode *next;

    LNode() {
        this->next = nullptr;
    }

    LNode(ElemType data) {
        this->data = data;
        this->next = nullptr;
    }

    void Print() {
        std::cout << this->data << std::endl;
    }

} LNode, *LNodePtr;

/*
    LinkList:单链表
*/
typedef struct LinkList {
    LNodePtr headPtr;
    LNodePtr tmpPtr;

    LinkList() {
        headPtr = new LNode();
    }

    void Print() {
        tmpPtr = headPtr->next;
        std::cout << "Data :" << std::endl;
        while (tmpPtr != nullptr) {
            std::cout << tmpPtr->data;
            std::cout << " ";
            tmpPtr = tmpPtr->next;
        }
        std::cout << std::endl;
    }

    LNodePtr HeadInsert(LNodePtr node) {
        tmpPtr = headPtr;
        node->next = tmpPtr->next;
        tmpPtr->next = node;
        return node;
    }

    LNodePtr TailInsert(LNodePtr node) {
        tmpPtr = headPtr;
        while (tmpPtr->next != nullptr) {
            tmpPtr = tmpPtr->next;
        }
        tmpPtr->next = node;
        return node;
    }

    LNodePtr GetElem(int pos) {
        if (pos == -1) return headPtr;
        tmpPtr = headPtr;
        for (int i = 0; tmpPtr->next != nullptr; i++) {
            tmpPtr = tmpPtr->next;
            if (i == pos) {
                return tmpPtr;
            }
        }
        return nullptr;
    }

    LNodePtr LocateElem(ElemType val) {
        tmpPtr = headPtr;
        while (tmpPtr->next != nullptr) {
            tmpPtr = tmpPtr->next;
            if (tmpPtr->data == val) {
                return tmpPtr;
            }
        }
        return nullptr;
    }

    LNodePtr Insert(int pos, LNodePtr val) {
        LNodePtr pre = this->GetElem(pos - 1);
        if (pre == nullptr) return nullptr;
        val->next = pre->next;
        pre->next = val;
        return val;
    }

    LNodePtr Delete(int pos) {
        LNodePtr pre = this->GetElem(pos - 1);
        if (pre == nullptr) return nullptr;
        LNodePtr val = pre->next;
        pre->next = val->next;
        delete val;
        return pre->next;
    }

    int Length() {
        tmpPtr = headPtr;
        int len = 0;
        while (tmpPtr->next != nullptr) {
            tmpPtr = tmpPtr->next;
            len ++;
        }
        return len;
    }

} LList, *LListPtr;

int main() {
    LListPtr L = new LList();
    L->Print();

    L->HeadInsert(new LNode(2));
    L->HeadInsert(new LNode(3));
    L->HeadInsert(new LNode(4));
    L->TailInsert(new LNode(5));
    L->TailInsert(new LNode(6));
    L->TailInsert(new LNode(7));
    L->Print();

    L->GetElem(4)->Print();
    L->LocateElem(3)->Print();

    L->Insert(4, new LNode(9))->Print();
    L->Print();

    L->Delete(0)->Print();
    L->Print();

    cout<<L->Length()<<endl;

    return 0;
}